package class_0822Graph;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Queue;

/**
 * @author 90774
 */
public class GraphMethods {
    public static void createGraphByMatrix(Integer[][] matrix){
        return ;
    }
    public static void createGraph(Integer[][] matrix){
        Graph  graph = new Graph();
        //matrix[0][0]:from ,matrix[0][1]:to,matrix[0][2]:weight
        for(int i=0;i< matrix.length;i++){
            Integer from = matrix[i][0];
            Integer to = matrix[i][1];
            Integer weight = matrix[i][2];
            //生成对应的结点:编号+结点
            if(!graph.nodes.containsKey(from)){
                graph.nodes.put(from,new Node(from));
            }
            if(!graph.nodes.containsKey(to)){
                graph.nodes.put(to, new Node(to));
            }

            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);
            //生成对应的有向边.
            Edge edge = new Edge(weight,fromNode,toNode);
            fromNode.nexts.add(toNode);
            fromNode.out++;
            toNode.in++;
            fromNode.edges.add((edge));
            graph.edges.add(edge);
        }
    }
    public static void bfs(Node head) {
        if (head == null) {  // 检查头节点是否为空
            return;
        }
        Queue<Node> queue = new ArrayDeque<>();  // ArrayDeque实现的队列来存储要访问的节点
        HashSet<Node> set = new HashSet<>();  // HashSet来记录已访问的节点
        queue.add(head);  // 将头节点加入队列
        set.add(head);  // 将头节点标记为已访问
        while (!queue.isEmpty()) {  // 当队列不为空时，继续循环
            Node cur = queue.poll();  // 取出队列头部的节点
            System.out.println(cur.value);  // 处理当前节点的值（这里是输出节点的值）
            for (Node next : cur.nexts) {  // 遍历当前节点的所有邻接节点
                if (!set.contains(next)) {  // 如果邻接节点未被访问过
                    queue.offer(next);  // 将邻接节点加入队列
                    set.add(next);  // 将邻接节点标记为已访问
                }
            }
        }
    }
    public static void dfs(Node head) {
        if (head == null) {  // 检查头节点是否为空
            return;
        }
        Deque<Node> stack = new ArrayDeque<>();  // 使用ArrayDeque实现的栈来存储要访问的节点
        HashSet<Node> set = new HashSet<>();  // 使用HashSet来记录已访问的节点
        stack.push(head);  // 将头节点压入栈中
        set.add(head);  // 将头节点标记为已访问
        System.out.println(head.value);  // 处理当前节点的值（这里是输出节点的值）

        while (!stack.isEmpty()) {  // 当栈不为空时，继续循环
            Node cur = stack.poll();  // 弹出栈顶节点
            for (Node next : cur.nexts) {  // 遍历当前节点的所有邻接节点
                if (!set.contains(next)) {  // 如果邻接节点未被访问过
                    stack.push(cur);  // 将当前节点重新压入栈中
                    stack.push(next);  // 将下一个节点压入栈中
                    System.out.println(next.value);  // 处理下一个节点的值
                    set.add(next);  // 将下一个节点标记为已访问
                    break;  // 退出当前循环，以便深入到新节点
                }
            }
        }
    }

}
